package com.mao.interview.prime;

/**
 * 求n范围内的所有质数，2种方法，根号求余法和位图法
 *
 */
public class PrimeCaculator {

	public static void main(String[] args) {
		printPrime(100);
	}

	public static void printPrime(int n) {
		sqrtFind(n);
		// bitmapFind(n);
	}

	private static void bitmapFind(int n) {
		int[] map = new int[n + 1];
		for (int i = 0; i <= n; i++) {
			map[i] = 0;
		}
		for (int i = 2; i <= n; i++) {
			int j = 2;
			int index = i * j;
			while (index <= n) {
				map[index] = 1;
				j++;
				index = i * j;
			}
		}
		int count = 0;
		for (int i = 2; i <= n; i++) {
			if (map[i] == 0) {
				System.out.println("发现质数 " + i);
				count++;
			}
		}
		System.out.println("共有" + count + "个质数");
	}

	private static void sqrtFind(int n) {
		int count = 0;
		if (n < 2) {
			return;
		}
		int i = 0;
		for (i = 2; i <= n; i++) {

			int k = (int) Math.sqrt(i);
			int j = 2;
			for (; j <= k; j++) {
				if (i % j == 0) {
					break;
				}
			}

			if (j > k) {
				count++;
				System.out.println("发现质数" + i);
			}
		}

		System.out.println("共有" + count + "个质数");
	}
}
